package com.ljx.offer;

import java.util.HashSet;

/**
 * @author 李捷禧
 * Date: 2023/3/11
 * ClassName: CTest
 */

public class C3 {
    /**
     * 这种是最普通的实现的方式
     * @param nums
     * @return
     */
    public int fid(int[] nums){
        HashSet<Integer> hashSet = new HashSet<>();
        for (int num : nums) {
            if(hashSet.contains(num)){
                return num;
            }
            hashSet.add(num);
        }
        return -1;
    }

    /**
     * 官方题解里面最优美的方式
     * 题目要求：找出两个相同的数
     *      如果是map，其实很容易就找到。
     *      题目条件：在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内
     *      所以，如果每个数都在对应的位置上（例如nums[0]=0, nums[i]=i），那其实就很好解决，
     * 思路：
     *     遍历数组，假设nums[i] = value, 那就将value的值放到nums[value]上，
     *     如果nums[value]上的值刚好也等于value，那说明nums[i]=nums[value]=value。结果已经出来了
     * @param nums
     * @return
     */
    public int fid2(int[] nums) {
        int i = 0;
        while(i < nums.length){
            // 数组第i个值刚好等于i, 则进入下一个
            if(nums[i] == i){
                i++;
                continue;
            }
            // 判断nums[value]是否等于value，等于则找到结果
            if(nums[nums[i]] == nums[i])
                return nums[i];
            // 否则，互换位置。记住，这里i不变，所以下次循环还是会处理这个值，
            int tmp = nums[nums[i]];
            nums[nums[i]] = nums[i];
            nums[i] = tmp;
        }
        return -1;
    }
}
